/**
 * 输入一个链表，输出该链表中倒数第k个节点
 * 给定一个链表: 1->2->3->4->5, 和 k = 2.
 * 返回链表 4->5.
 */
/**
 * 栈
 */
var getKthFromEnd = function (head, k) {
  var stack = []
  var ans = []
  while (head) { // 所有节点入栈
    stack.push(head);
    head = head.next;
  }
  while (k > 0) {
    ans = stack.pop();
    k--;
  }
  return ans;
}

/**
 * 快慢指针
 */
var getKthFromEnd = function (head, k) {
  let fast = head
  let slow = head
  let cloneK = k - 1
  while (cloneK && fast) {
    fast = fast.next
    cloneK--
  }
  if (!fast) return null
  while (slow.next && fast.next) {
    slow = slow.next
    fast = fast.next
  }
  return slow
}